1. Field of the Invention
The present invention relates to a privacy communication technique for transmitting numerical data through a public network or a broadcasting network, more particularly, to a technique using an elliptic curve thereto.
2. Description of Related Arts
A public key cryptosystem facilitates the management of cipher keys for respective correspondents, while it makes deciphering cryptography more intricate. In addition, the public key enables only the designated correspondents to decipher data through a private communication, should the data be eavesdropped. Thus, it is an essential technique to transmit anonymous data as well as to validate and identify the correspondents through the public network. Such a private communication has been already in practical use, and application is known as a broadcasting system in which programs are available only to those who are provided with deciphering equipments, and as rental laser disks which are available only to those who have deciphering equipments.
Explained in the followings is the privacy communication through the public key cryptosystem and difficulty of deciphering which is the basis for reliability thereof, and such reliability is dependent on difficulty of the discrete logarithm problem over finite abelian groups. "Intractable Problems in Number Theory", E. Bach, Advances in Cryptology-Proceedings of Crypto '88. Lecture Notes in Computer Science, 403(1988), pages 77-93, Springer-Verlag. discusses such difficulty.
______________________________________ &lt;Notation&gt; ______________________________________ p: a prime number Galois Field(p), or GF(p): a finite field with p elements, or a complete residue system modulo p g: a primitive root of GF(p), or an integer such that becomes 1 when raised to the p-1th power as a residue modulo p a: an arbitrary positive integer, 1 .ltoreq. a .ltoreq. p - 1 b: an arbitrary positive integer, 1 .ltoreq. b .ltoreq. p - 1 .alpha.: a residue of g.sup.a modulo p, .alpha. .ident. g.sup.a (mod p) .beta.: a residue of g.sup.b modulo p, .beta. .ident. g.sup.b (mod p) k: a residue of g to the (a .times. b)th power, k .ident. g.sup.a-b (mod p) ______________________________________
Although it is easy to find, .alpha. using g, p and a, it is quite difficult, even with help of sophisticated computers, to find a using g, p, and .alpha. when p is a large prime number. In other words, it is difficult to find an index using a residue, a primitive root, and an element, as is explained in "AN INTRODUCTION TO THE THEORY OF NUMBERS", G. H. HARDY & E. M. WRIGHT, OXFORD UNIVERSITY PRESS.
In the following, procedures of the privacy communication is explained with referring to FIG. 1. In the privacy communication using a public network, p=11 and g=2, or the public keys, have been previously provided to users A and B. Each of them selects and withholds a privacy key, or arbitrary integers a=4 and b=8, respectively. The user A notifies .alpha.=5 to the user B while the user B notifies .beta.=3 to the user A. Then with the following congruences, they find k=4, or a common key which is used and withheld between two of them.
______________________________________ k .ident. g.sup.ab .ident. (g.sup.a).sup.b (mod p) .ident. .alpha..sup.b (mod p) .ident. (g.sup.b).sup.a (mod p) .ident. .beta..sup.a (mod ______________________________________ p)
As previously mentioned, because it is difficult to find k using p, g, .alpha., and .beta., it is almost impossible to find k unless one knows a and b, which means that a third party is not able to understand the data should he/she receive them.
The privacy communication flexibly replaces the users(adding new users/cancelling the users). More precisely, the privacy communication will be also available to users C and D when each of them selects and withholds the privacy key, or arbitrary integers c and d, respectively, and the common keys g.sup.a-b, g.sup.a-c, g.sup.a-d, b.sup.b-c, g.sup.b-d, and g.sup.c-d are exchanged among the users A through D. In addition, reliability is further enhanced by replacing the privacy key regularly, for instance, replacing a with a' in the first 6 months, and with a" in the next 6 months. It also should be noted that coincidence(a=b) of the privacy keys is decreased in reverse proportion to the largeness of the prime number.
The privacy transmission is also applicable to image data transmission such as one through facsimile machines. For instance, in a subscription television service(STV), the privacy transmission coupled with deciphering equipments provided to subscribers makes it possible to transmit the data only to those who have paid the charges. Also, installing such deciphering equipments in the seats of jetliners contributes to loaning portable data storage media storing ciphered image/audio data such as laser disks and magnetic tapes in terms of preventing the stealing and failure in returning of these media. More precisely, since each jetliner or air route is provided with different common keys, ciphering methods, and models of deciphering equipments, these media are repeatable only when they are set into the appropriate deciphering equipments. Another option for the prevention of stealing and failure in returning of these media would be to provide an automatic data cancelling function that cancels the data once the data are deciphered. However, the latter is not preferable because providing such a function to each deciphering equipment may result in adding unnecessary weight to the jetliners as well as receiving bad reputation from the passengers.
Today's cable/radio transmission system essentially transmits the data in bits consisting of codes 1 and 0 in order to prevent noise, and because of hardware and software programs facility as well as the binary notation applied in most of the computers. Even an AF modulation analogue signal is converted so as to have a wave height in every time unit for the bit transmission. Therefore, the data transmission is acknowledged as a sequential transmission of an integer expressed in the binary notation if the data are divided into units.
Accordingly, having previously fix the number of bits in the unit makes it possible to transmit the data as numerical data h.sub.1, h.sub.2, . . . h.sub.i. Therefore, ciphering h.sub.1, h.sub.2, . . . h.sub.i with k enables the users to exploit the privacy communication. Three conceivable ciphering methods are, for instance, shown in FIG. 2. In the first method, the data h.sub.1, h.sub.2, . . . h.sub.i are multiplied with k, and in the second method, the data h.sub.1, h.sub.2, . . . h.sub.i are added to k. In the third method, the data h.sub.1, h.sub.2, . . . h.sub.i are disturbed with k, in other words, provided that k has the same bit length as that of the data h.sub.1, h.sub.2, . . . h.sub.i, "1" in k reverses the corresponding bits in the data h.sub.1, h.sub.2, . . . h.sub.i while "0" bit allows the corresponding bits to remain the same. Such data are easily deciphered by the users possessing k, while the third party has a hard time to decipher such data unless he/she knows k even when these data are eavesdropped by or happened to be transmitted to him/her.
Further improvement, modification, and various application have been continuously added to the public key cryptosystem in order to answer the following necessities for;
(1) having an integer with an order as large as possible to meet advancement of the computers capable of finding a large prime number, although a primitive root thereof can not be found easily with these computers.
(2) maintaining deciphering difficult by exploiting the developments of massive computers, and by applying the theory of numbers such as a decomposition method, a higher-order reciprocity, and a prime number theory as fully as possible.
(3) reducing steps and calculations in ciphering the data with the common key due to a capacity limit of hardware.
(4) minimizing the bit length of the ciphered data.
(5) validating/identifying the correspondents in order to prevent the transmission under an alias.
More precisely, not only p and g are replaced regularly, but also p is chosen so that p+1 and p-1 have also prime factors for above (1) and (2). For (3) and (4), a ciphering method with reduced calculations and maintaining difficulty in deciphering has been studied, since the first ciphering method mentioned above requires myriads of calculations, and results in generating the common key with many digits, while the second and third methods facilitate deciphering. Also researches are being carried out on more sensitive deciphering method through which the data are not deciphered until the common key is proved intact for (5). Also, more compact and inexpensive deciphering equipments as well as improved bit distributors are being developed as is introduced in "Gendai Ango Riron", Shinichi Ikeno and Kenji Koyama, Denshintsushin Gakkai. Moreover, the public key cryptography using a common cipher key and a common decipher key, and the transmission method thereof are being developed. Therefore, it is to be noted that the common keys are used both in ciphering and deciphering hereinafter.
In the following, mathematical and programmatic aspects of the discrete logarithm problem are described.
In order to increase the speed and enhance reliability in the public key cryptosystem, a technique to construct the difficult discrete logarithm problem is indispensable. Followings are examples of such construction of the discrete logarithm problem in the finite field(hereinafter referred to DLP) and that in the elliptic curve(hereinafter referred to EDLP).
______________________________________ DPL &lt;Notation&gt; ______________________________________ q: a power of a large prime number GF(q): a finite filed with q element g: a primitive root to GF(q) ______________________________________
Let y be an element of GF(q). Then, DLP is a problem of finding an integer.times.(0.ltoreq.x.ltoreq.q-1) such that y=g.sup.x if such an integer x exists.
In order to make DLP difficult for the third party, it is necessary to choose q so that q-1 has prime factors having more than or equal to 160 digits. The same logic is applied here as the one in case of the residue system modulo p, wherein it is necessary to choose a large prime number as p, and an integer having a large order as g, or to choose p so that p-1 has a large prime factor. Since sophisticated computers of these days choose such q easily, it is quite easy to construct such DLP as well.
However, for such DLP, study on mathematical properties such as a property of factors has been pursued and various solutions have been presented in a book such as "Fast Evaluation of Logarithms in Fields of Characteristic Two", IEEE TRANSACTIONS ON INFORMATION THEORY, pages 587-584, IT-30(1984). Thus, DLP is solvable in shorter time these days if DLP is constructed over a small finite field, which, at the same time, means that deciphering is getting easier.
A general theory of an algebraic aspect of the finite field is on "MODERN ALGEBRA", B. L. Van der Waerden, Springer.
EDLP
Another method to construct the discrete logarithm problem is to apply an elliptic curve as the finite abelian group, or construct EDLP as is introduced in "A Course in Number Theory and Cryptography", N. Koblitz, Springer-Verlag, 1987, and "Use of Elliptic Curves in Cryptography", V. Miller, Proceedings of Crypto '85, Lecture Notes in Computer Science, 218(1986), pages 417-426, Springer-Verlag.
Since the study of solutions on EDLP have not been carried out much compared to that on DLP, applying the elliptic curve to the public key cryptosystem makes it possible to cipher and decipher the data more easily and faster without reducing reliability thereof.
The elliptic curve means an abelian manifold, or a projective algebraic curve with an irreducible and a non-singular genus 1.
Let the characteristic of a finite field K.noteq.2, 3, PA1 then, it is expressed as in an equation EQU Y.sup.2 =X.sup.3 +a.times.X+b PA1 p: a prime PA1 r: a positive integer PA1 q: a power of p PA1 F.sub.q : a finite field with q elements PA1 K: a field (include a finite field) PA1 ch(K): the characteristics of a field K PA1 K.sup.r : the multiplicative group of a field K PA1 K: a fixed algebraic closure of K PA1 E: an elliptic curve PA1 #A: the cardinality of a set A PA1 o(t): the order of an element t of a group PA1 Z: the ring of integers PA1 (j-1) Two elliptic curves are isomorphic (over K) if and only if they have the same j-invariant. PA1 (j-2) For any element j.sub.0 .epsilon.K, there exists an elliptic curve defined over K with j-invariant equal to j.sub.0. For example, if j.sub.0 .noteq.0,1728, we let EQU E:y.sup.2 +xy=x.sup.3 -36/(j.sub.0 -1728)x-1/(j.sub.0 -1728). PA1 Method: (1) Find a non-trivial subgroup &lt;2.sup.t P&gt; &lt;P&gt; whose order is prime to p=ch(K).
and let a and b be elements of K PA2 If we remark a field of definition K of E, we write E/K. PA2 (2) Embed &lt;2.sup.t P&gt; into the multiplicative group of a suitable extension field of K via an injective homorphism constructed by Weil pairing. PA2 (3) Change EDLP on E to the base P into EDLP on E to the base kP. (Since all of the prime factors of #&lt;kP&gt; are small, we can easily solve such EDLP.)
Further reference of pure mathematic theory is on "INTRODUCTION TO THE ARITHMETIC THEORY OF AUTOMORPHIC FUNCTIONS", CHAPTER 4 ELLIPTIC CURVES, Goro Shimura, Iwanami Shoten, "EINFUEHRLING IN DIE THEORIE DER ALGEBRASCHEN ZAHLEN UND FUNKTIONEN", KAPITEL IV Algebraische Funktionen Ueber Den KomplexenZahlkoeper, MARTIN EICHLER, BIRKHAEUSER BERLAG.
In the followings, explanation of the basic mathematics is quoted from "On Ordinary Elliptic Curve Cryptosystems", Abstract of Proceedings of ASIACRYPTO, '91, 1991, A. Miyaji. one of the investors of the present invention for further explanation.
QUOTE
Notation
Background on Elliptic Curves
We briefly describe some properties of alliptic curves that we will use later. For more information, see [Sil]. In the following, we denote a finite field F.sub.q by K.
Basic Facts
Let E/K be an elliptic curve given by the equation, called the Weierstrass equation, EQU E: y.sup.2 +a.sub.1 xy+a.sub.3 y=x.sup.3 +a.sub.x x.sup.2 +a.sub.4 +a.sub.6 (a.sub.1, a.sub.3, a.sub.2, a.sub.4, a.sub.6 .epsilon.K).
The j-invariant of E is an element of K determined by a.sub.1, a.sub.3, a.sub.2, a.sub.r and a.sub.6. It has important properties as follows.
Then j-invariant of E is j.sub.0.
The Group Law
A group law is defined over the set of points of an elliptic curve, and the set of points of an elliptic curve forms an abelian group. We denote the identity element .infin.. After this, for m.epsilon.Z and P.epsilon.E, we let EQU mP=P+ . . . +P (m terms) for m&gt;0, EQU OP=.infin., and EQU mP=(-m)(-P) for m&lt;0.
The set of K-rational points on the elliptic curve E, denotes E(K), is EQU E(K)=[(x,y).epsilon.K.sup.2 .vertline.y.sup.2 +a.sub.1 xy+a.sub.3 x.sup.3 +a.sub.2 x.sup.2 +a.sub.4 x+a.sub.6 ]U[.infin.]
E(K) is a subgroup of E and a finite abelian group. So we can define the discrete logarithm problem over it.
[Sil] J. H. Silverman, "The Arithmetic of Elliptic Curves", GTM106, Springer-Verlag, New York, 1986
UNQUOTE
Explained in the followings with referring to FIG. 7 is a flow of a ciphering method used through the privacy communication in the public key cryptosystem with an elliptic curve, which is similar to the privacy communication based on ElGamal ciphering in the finite field.
&lt;Notation&gt;
E: an elliptic curve
q: a power of p (p.sup.r)
E(GF(q)): the group of elements of GF(q) on the elliptic curve E defined over GF(q)
1) Key generation
Select E defined over GF(q). Comparison between GF(q) and E(GF(q)) are as follows:
______________________________________ GF(q) E(GF(q)) unit element: 1 unit element: infinite point multiplication addition y = g.sup.x Y = P + . . . + P (x terms) = xP (y and g are elements (Y and P are elements of GF(q), x is an integer) of E(GF(q)), x is an integer) result of the multiplication P.sub.1 + P.sub.2 represents a point P.sub.3, is a scalor product which is symmetric with respect to the x-axis to P.sub.3, an intersection between E and a straight line passing P.sub.1 and P.sub.2 as shown in FIG. 4. (When P.sub.1 = P.sub.2, the straight line passing P.sub.1 and P.sub.2 represents a tangential line of E at P.sub.1) ______________________________________
Let P.sub.1 be an element of E(GF(q)) with a large order and having the same property as g in GF(q), which means that P and E(GF(q)) are the public keys. The user B selects an integer x.sub.B and computes Y.sub.B, EQU Y.sub.B =x.sub.B P [1]'
Then the user B withholds X.sub.B as the privacy key while informs Y.sub.B to all the other users.
2) Ciphering
Suppose the user A sends a message M to the user B through the privacy communication.
Having secretly selected a random number k, the user A produces two sets of cryptography C.sub.1 and C.sub.2 from M using k and Y.sub.B.
Thus, EQU C.sub.1 =kP [2]' EQU C.sub.2 =M+kY.sub.B [ 3]'
Then, the user A sends C.sub.1 and C.sub.2 to the user B.
3) Deciphering
Having received C.sub.1 and C.sub.2, the user B finds M using EQU M+x.sub.B C.sub.1 =C.sub.2 [ 4]'
It is to be noted that all expressions [1]', [2]', [3]', and [4]' are proceeded in E(GF(q)), and M, Y.sub.B, and P are elements of E(GF(q)).
Concerning the calculation of x.sub.B and Y.sub.B (x.sub.0, y.sub.0), or one demential numerical data and quadratic numerical data/an element of the elliptic curve, other data are provided so that Y.sub.B (x.sub.0, y.sub.0) can be found either with x.sub.0 or y.sub.0, or a method that uses either x.sub.0 or y.sub.0 is applied.
Replacing the elements of the finite filed with those of the elliptic curve, and replacing the multiplication in the finite field with the addition in the elliptic curve make it possible to convert DLP into EDLP, therefore enables the public key cryptosystem to have its reliability based on difficulty of EDLP. In other words, EDLP is: let P be a base point(=g in DLP) of E(GF(q)), and find an integer x such that Y=x*P, if such integer x exists.
Researches on application of EDLP to the public key cryptosystem were carried out for the following reasons:
a) Given the fact that an effective solution for EDLP has been under the quest, GF(q) can be smaller, therefore making it possible to increase the speed by decreasing the calculations for ciphering and deciphering while maintaining reliability.
b) In order to maintain reliability of the public key cryptosystem, the finite abelian groups should be replaced regularly. For instance, it should be replaced at the renewal of the contracts in STV, and different finite abelian groups should be applied to respective jetliners. Since each q has a single finite field when the finite field is used for the privacy communication, calculation necessary for ciphering/deciphering, or an algorithm, should be changed in accordance with the finite abelian groups. More precisely, a calculation over GF(7) is proceeded per block consisting of 1-byte(8 bits), while a calculation over GF(17) is proceeded per 2 blocks. On the other hand, since each q has abundant elliptic curves over GF(q), the elliptic curve can be replaced without replacing the finite field used as the base for ciphering/deciphering.
However, because it is difficult to find the number of the elements of GF(q) of the elliptic curve, denoted as #E(GF(q)), finding #E(GF(q)) such that is divisible by a large prime number having more than or equal to 30 digits becomes more difficult. "A Course in Number Theory and Cryptography" also deals with such difficulty.
In conclusion, it can be said that when constructing the public key cryptosystem with an elliptic curve, it is necessary to construct the elliptic curve so that #E(GF(q)) has a large prime factor having more than or equal to 30 digits. The same logic is applied here as the one explained in that q-1 needs to have a large prime factor.
In the following, the method to construct an elliptic curve applicable as a finite abelian group is described.